package codingInterviews.chapter01_整数;

/**
 * @author https://gitee.com/W_Jun
 * @date 2022-03-25 22:05
 * @Description 输入2个int型整数，它们进行除法计算并返回商，
 *              要求不得使用乘号“/”、除号"%"及求余符号"%"。
 *              当发生溢出时，返回最大的整数值。假设除数不为0。
 *              例如，输入15和2，输出15/2的结果，即7.
 */
public class Q1 {
    public static void main(String[] args) {
        int i = divide(15, 2);
        System.out.println(i);
    }

    /**
     * @param dividend
     * @param divisor
     * @return int
     * @Description 第一个参数是被除数，第二个参数是除数。
     *              全部转化成负数，然后再判断符号，这样溢出的情况就会只剩一种。
     *              先判断发生溢出的情况: (-2^31)/(-1) --返回最大的整数值。
     *              不发生溢出的话，就将除法转化成减法。
     *              简单的做法：
     *                  被除数不断减去除数，复杂度为O(N)。
     *              优化的做法：当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，
     *                  如果是，则继续判断被除数是否大于除数的4倍，8倍等。如果被除数最多
     *                  大于除数的2^k倍，那么将被除数减去除数的2^k倍，然后将剩余的被除数
     *                  重复前面的步骤。由于每次将除数翻倍，因此优化后的时间复杂度O(logN).
     * */
    public static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {//0x80000000是最小的int数，即MIN_VALUE
            return Integer.MAX_VALUE;
        }
        //定义一个标识，如果最后这个标识为1，就说明被除数和除数都是负数。
        /*
        * 至于为什么标识初始值为2，我认为的合理解释是：
        * 1. 如果被除数为正数，除数为负数，那么结果是负数。所以，divideCore方法的计算结果需要添加负号。
        * 2. 如果被除数为负数，除数为正数，同上。
        * 3. 如果被除数为正数，除数为正数，那么结果是正数，不需要再改变divideCore方法的结果。
        * 4. 如果被除数为负数，除数为负数，同上。
        * 从这四点可能的情况来看，
        * 只有第1和第2点，会将标识减去1，标识变为1。而第3点标识不变，为2。第4点，标识减去2次，变为0.
        * 所以我们利用标识最后是否为1来判断是否为divideCore的结果添加负号。如果是1，就添加，不是1就不添加。
        * */
        int negative = 2;

        //如果被除数是正数，将它转化为负数，并且，将标识减去1。否则（被除数是正数）不做任何操作
        if (dividend > 0) {
            negative--;
            dividend = - dividend;
        }
        //如果除数是正数，将它转化为负数，并且，将标识减去1
        if (divisor > 0) {
            negative--;
            divisor = - divisor;
        }

        //此时，被除数和除数都是负数了，可以调用divideCore这个计算的核心方法了。
        int result = divideCore(dividend, divisor);//这个结果肯定是个正数

        //运算的结果需要利用标识来判断是否添加负号。
        return negative == 1 ? -result : result;
    }

    /**
     * 这个方法里定义的被除数和除数都是负数
     * */
    private static int divideCore(int dividend, int divisor) {
        int result = 0;

        //注意此方法中的被除数和除数都是负数，如果被除数比除数大，那么需要进行判断被除数是除数的多少倍
        while (dividend <= divisor) {
            int quotient = 1;//在相等的情况下，或被除数绝对值不超过除数的2倍 的情况下，商为1
            int value = divisor;//用value记录除数乘以2^k，表示的是：被除数最多大于除数的2^k。
            //我们需要用被除数减去value的结果作为新的被除数
            while (value >= 0xc0000000 && dividend <= value + value) {//0xc0000000是 -2^30
                //如果value在这个区间[-2^30, 0), 且被除数比value的2倍还小（就是要判断是除数的2^k，这个k究竟能到多少，商就是多少）
                //那么就将value加倍，即乘以2，同时商也加倍
                value += value;
                quotient += quotient;
            }
            result += quotient;
            dividend -= value;//每次用被除数减去除数的2^k倍，利用剩余的值作为被除数

        }

        //注意此方法中的被除数和除数都是负数，如果被除数比除数小，那么商为0
        return result;
    }
}
